{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 经典查找算法\n",
    "\n",
    "在计算机科学中，查找算法是数据结构中最基本的操作之一。无论是在数据库系统中搜索特定记录，还是在编程语言中实现高效的数据访问，查找算法都是不可或缺的一部分。选择合适的查找算法可以极大地提高系统的性能，减少资源消耗，并改善用户体验。不同的查找算法适用于不同类型的存储结构和数据集，因此理解每种算法的工作原理及其适用场景对于开发人员来说至关重要。\n",
    "\n",
    "**下面是一个关于几种常见查找算法特点的简要概述表：**\n",
    "\n",
    "### 引言\n",
    "\n",
    "在计算机科学中，查找算法是数据结构中最基本的操作之一。无论是在数据库系统中搜索特定记录，还是在编程语言中实现高效的数据访问，查找算法都是不可或缺的一部分。选择合适的查找算法可以极大地提高系统的性能，减少资源消耗，并改善用户体验。不同的查找算法适用于不同类型的存储结构和数据集，因此理解每种算法的工作原理及其适用场景对于开发人员来说至关重要。\n",
    "\n",
    "下面是一个关于几种常见查找算法特点的简要概述表：\n",
    "\n",
    "| 查找算法   | 时间复杂度（最好/平均/最坏）     | 空间复杂度 | 数据结构   | 特点                               |\n",
    "|-----------|--------------------------------|------------|------------|----------------------------------|\n",
    "| 顺序查找   | O(1)/O(n)/O(n)                 | O(1)       | 数组/链表  | 简单，无需排序                      |\n",
    "| 二分查找   | O(log n)/O(log n)/O(log n)     | O(1)       | 排序数组   | 快速，但需要数据预排序              |\n",
    "| 二叉查找树 | O(1)/O(log n)/O(n)             | O(n)       | 二叉树     | 动态，插入删除操作也较快            |\n",
    "| 散列查找   | O(1)/O(1)/O(n)                 | O(n)       | 散列表     | 快速访问，依赖于好的哈希函数        |\n",
    "| 插值查找   | O(log log n)/O(log log n)/O(n) | O(1)       | 排序数组   | 在均匀分布的数据上表现优于二分查找 |\n",
    "| 跳跃查找   | O($\\sqrt{n}$)/O($\\sqrt{n}$)/O($\\sqrt{n}$)              | O(1)       | 排序数组   | 在较大的数据集上比线性查找快       |\n",
    "| 红黑树     | O(log n)/O(log n)/O(log n)     | O(n)       | 平衡二叉树 | 自平衡，适合动态数据集              |\n",
    "| B树        | O(log n)/O(log n)/O(log n)     | O(n)       | 多路搜索树 | 优化了磁盘I/O操作                  |\n",
    "| B+树       | O(log n)/O(log n)/O(log n)     | O(n)       | 多路搜索树 | 常用于数据库索引                   |\n",
    "| B-树       | 不常用                         |            |            | 与B树相似，但在某些数据库系统中使用 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. 顺序查找（Linear Search）\n",
    "顺序查找是一种非常直接的查找方法，它适用于任何类型的数据结构，比如数组或链表。它的基本思想是从数据集合的第一个元素开始，逐个比较目标元素与集合中的每个元素，直到找到目标元素或者遍历完整个集合为止。这种方法不需要数据预处理，也不要求数据是有序的。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element 7 found at index 2\n"
     ]
    }
   ],
   "source": [
    "public class SequentialSearch {\n",
    "\n",
    "    /**\n",
    "     * 顺序查找方法\n",
    "     * @param arr 需要被搜索的数组\n",
    "     * @param target 要查找的目标元素\n",
    "     * @return 目标元素在数组中的索引，如果没有找到，则返回-1\n",
    "     */\n",
    "    public static int search(int[] arr, int target) {\n",
    "        for (int i = 0; i < arr.length; i++) {\n",
    "            if (arr[i] == target) {\n",
    "                return i; // 找到目标元素，返回其索引\n",
    "            }\n",
    "        }\n",
    "        return -1; // 没有找到目标元素，返回-1\n",
    "    }\n",
    "}\n",
    "\n",
    "// 测试\n",
    "int[] data = {5, 3, 7, 2, 8, 1};\n",
    "int target = 7;\n",
    "int index = SequentialSearch.search(data, target);\n",
    "if (index != -1) {\n",
    "    System.out.println(\"Element \" + target + \" found at index \" + index);\n",
    "} else {\n",
    "    System.out.println(\"Element \" + target + \" not found.\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. 二分查找（Binary Search）\n",
    "二分查找是一种高效的查找算法，它要求数据集事先已经被排序。算法的基本思想是每次都将搜索区间对半分割，通过比较中间元素与目标元素来决定下一步是在左半部分还是右半部分继续查找。这样每次比较都能排除掉一半的候选元素，大大减少了查找次数。\n",
    "\n",
    "### 二分查找的步骤\n",
    "\n",
    "1. **初始化边界**:\n",
    "   - 设定左边界 `left` 为数组的第一个元素的索引 `0`。\n",
    "   - 设定右边界 `right` 为数组的最后一个元素的索引 `arr.length - 1`。\n",
    "\n",
    "2. **循环条件**:\n",
    "   - 只要左边界不大于右边界（`left <= right`），就表示搜索区间内还有元素，继续搜索。\n",
    "\n",
    "3. **计算中间位置**:\n",
    "   - 使用公式 `int mid = left + (right - left) / 2` 来计算中间位置的索引。这样做的目的是为了避免 `(left + right) / 2` 导致整数溢出的问题。\n",
    "\n",
    "4. **比较并调整边界**:\n",
    "   - 检查中间位置的元素是否为目标值：\n",
    "     - 如果中间位置的元素等于目标值（`arr[mid] == target`），则找到了目标元素，返回该元素的索引。\n",
    "     - 如果中间位置的元素小于目标值（`arr[mid] < target`），则目标值在中间位置的右侧，因此更新左边界 `left = mid + 1`。\n",
    "     - 如果中间位置的元素大于目标值（`arr[mid] > target`），则目标值在中间位置的左侧，因此更新右边界 `right = mid - 1`。\n",
    "\n",
    "5. **结束条件**:\n",
    "   - 如果循环结束后还没有找到目标值，则返回 `-1` 表示目标元素不在数组中。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element 7 found at index 6\n"
     ]
    }
   ],
   "source": [
    "public class BinarySearch {\n",
    "\n",
    "    /**\n",
    "     * 二分查找方法\n",
    "     * @param arr 已经排序的数组\n",
    "     * @param target 要查找的目标元素\n",
    "     * @return 目标元素在数组中的索引，如果没有找到，则返回-1\n",
    "     */\n",
    "    public static int search(int[] arr, int target) {\n",
    "        int left = 0;\n",
    "        int right = arr.length - 1;\n",
    "        \n",
    "        while (left <= right) {\n",
    "            int mid = left + (right - left) / 2; // 防止溢出\n",
    "            if (arr[mid] == target) {\n",
    "                return mid; // 找到目标元素，返回其索引\n",
    "            } else if (arr[mid] < target) {\n",
    "                left = mid + 1; // 在右半部分继续查找\n",
    "            } else {\n",
    "                right = mid - 1; // 在左半部分继续查找\n",
    "            }\n",
    "        }\n",
    "        return -1; // 没有找到目标元素，返回-1\n",
    "    }\n",
    "}\n",
    "\n",
    "// 测试\n",
    "int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};\n",
    "int target = 7;\n",
    "int index = BinarySearch.search(data, target);\n",
    "if (index != -1) {\n",
    "    System.out.println(\"Element \" + target + \" found at index \" + index);\n",
    "} else {\n",
    "    System.out.println(\"Element \" + target + \" not found.\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. 二叉查找树（Binary Search Tree, BST）\n",
    "好的，接下来我们将详细介绍二叉查找树（Binary Search Tree，BST）的相关内容，包括概念、步骤、Java实现、注释和测试方法。\n",
    "\n",
    "二叉查找树是一种特殊的二叉树，其中每个节点具有以下特性：\n",
    "- 节点的左子树只包含键值小于节点键值的节点。\n",
    "- 节点的右子树只包含键值大于节点键值的节点。\n",
    "- 左右子树也分别必须是二叉查找树。\n",
    "- 没有键值相同的节点。\n",
    "\n",
    "这些性质使得二叉查找树成为一种非常有用的动态数据结构，因为它支持高效的插入、删除和查找操作。\n",
    "\n",
    "\n",
    "**二叉查找树的查找步骤如下：**\n",
    "1. 从根节点开始。\n",
    "2. 如果根节点为空，则表示树中没有要查找的键值。\n",
    "3. 如果当前节点的键值等于要查找的键值，则查找成功。\n",
    "4. 如果当前节点的键值大于要查找的键值，则在当前节点的左子树中递归执行查找。\n",
    "5. 如果当前节点的键值小于要查找的键值，则在当前节点的右子树中递归执行查找。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element 6 found in the tree.\n"
     ]
    }
   ],
   "source": [
    "// 定义二叉树节点类 每个节点包含键值 `key` 和指向左右子节点的引用 `left` 和 `right`\n",
    "public static class TreeNode {\n",
    "    int key;\n",
    "    TreeNode left, right;\n",
    "\n",
    "    public TreeNode(int item) {\n",
    "        key = item;\n",
    "        left = right = null;\n",
    "    }\n",
    "}\n",
    "\n",
    "public class BinarySearchTree {\n",
    "    // 创建一个树 指向树根节点的引用 root\n",
    "    public TreeNode root;\n",
    "\n",
    "    /**\n",
    "     * 查找方法 用于查找给定键值的节点，它调用私有的递归方法 searchRec 来实际执行查找\n",
    "     * @param key 要查找的键值\n",
    "     * @return 如果找到键值，则返回对应的TreeNode对象；否则返回null\n",
    "     */\n",
    "    public TreeNode search(int key) {\n",
    "        return searchRec(root, key);\n",
    "    }\n",
    "\n",
    "    // 递归查找方法 用于在树中查找指定键值的节点\n",
    "    public TreeNode searchRec(TreeNode node, int key) {\n",
    "        // 树为空或找到键值\n",
    "        if (node == null || node.key == key) {\n",
    "            return node;\n",
    "        }\n",
    "\n",
    "        // 键值小于当前节点的键值，则在左子树中查找\n",
    "        if (key < node.key) {\n",
    "            return searchRec(node.left, key);\n",
    "        }\n",
    "\n",
    "        // 键值大于当前节点的键值，则在右子树中查找\n",
    "        return searchRec(node.right, key);\n",
    "    }\n",
    "}\n",
    "\n",
    "// 测试\n",
    "BinarySearchTree bst = new BinarySearchTree();\n",
    "// 构建二叉查找树\n",
    "bst.root = new TreeNode(8);\n",
    "bst.root.left = new TreeNode(3);\n",
    "bst.root.right = new TreeNode(10);\n",
    "bst.root.left.left = new TreeNode(1);\n",
    "bst.root.left.right = new TreeNode(6);\n",
    "bst.root.right.right = new TreeNode(14);\n",
    "\n",
    "// 查找元素\n",
    "int target = 6;\n",
    "TreeNode result = bst.search(target);\n",
    "if (result != null) {\n",
    "    System.out.println(\"Element \" + target + \" found in the tree.\");\n",
    "} else {\n",
    "    System.out.println(\"Element \" + target + \" not found in the tree.\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. 散列查找（Hashing）\n",
    "\n",
    "散列查找是一种通过散列函数将关键字映射到散列表中的某个位置来实现快速查找的技术。理想情况下，散列函数应该是均匀分布的，以避免过多的冲突。当发生冲突时，即两个不同的关键字映射到了同一个位置，可以采用多种解决策略，如链地址法（Separate Chaining）或开放寻址法（Open Addressing）。\n",
    "\n",
    "**散列查找的基本步骤如下：**\n",
    "1. 选择一个合适的散列函数，将关键字转换为散列表的索引。\n",
    "2. 如果没有冲突，则直接访问该索引位置的数据。\n",
    "3. 如果发生冲突，根据所选的冲突解决策略来处理。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element 34 is found in the hash table.\n"
     ]
    }
   ],
   "source": [
    "import java.util.LinkedList;\n",
    "\n",
    "public class HashTable {\n",
    "\n",
    "    // 散列表的大小\n",
    "    private static final int TABLE_SIZE = 10;\n",
    "\n",
    "    // 使用LinkedList作为桶（bucket）\n",
    "    private LinkedList<Integer>[] table;\n",
    "\n",
    "    public HashTable() {\n",
    "        // 使用一个 LinkedList 数组作为内部数据结构，每个 LinkedList 代表一个桶，用来存放具有相同散列值的关键字\n",
    "        table = new LinkedList[TABLE_SIZE];\n",
    "        for (int i = 0; i < TABLE_SIZE; i++) {\n",
    "            table[i] = new LinkedList<>();\n",
    "        }\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 散列函数 实现了简单的散列函数，通过取模运算将关键字映射到散列表的一个位置\n",
    "     * @param key 散列的关键字\n",
    "     * @return 散列后的索引\n",
    "     */\n",
    "    private int hashFunction(int key) {\n",
    "        return key % TABLE_SIZE;\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 插入方法 用于向散列表中插入一个新的关键字，首先计算关键字的散列值，然后将关键字添加到对应桶的链表中\n",
    "     * @param key 要插入的关键字\n",
    "     */\n",
    "    public void insert(int key) {\n",
    "        int index = hashFunction(key);\n",
    "        table[index].add(key);\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 查找方法 用于在散列表中查找一个关键字，首先计算关键字的散列值，然后检查对应桶的链表中是否存在该关键字\n",
    "     * @param key 要查找的关键字\n",
    "     * @return 如果找到关键字，则返回true；否则返回false\n",
    "     */\n",
    "    public boolean search(int key) {\n",
    "        int index = hashFunction(key);\n",
    "        return table[index].contains(key);\n",
    "    }\n",
    "}\n",
    "\n",
    "\n",
    "// 测试\n",
    "HashTable ht = new HashTable();\n",
    "int[] keys = {23, 45, 12, 56, 78, 34, 90, 21, 65, 32};\n",
    "// 插入数据\n",
    "for (int key : keys) {\n",
    "    ht.insert(key);\n",
    "}\n",
    "// 查找数据\n",
    "int target = 34;\n",
    "if (ht.search(target)) {\n",
    "    System.out.println(\"Element \" + target + \" is found in the hash table.\");\n",
    "} else {\n",
    "    System.out.println(\"Element \" + target + \" is not found in the hash table.\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. 插值查找（Interpolation Search）\n",
    "\n",
    "插值查找是一种改进的查找算法，它特别适用于元素分布均匀的大规模有序数组。与二分查找相比，插值查找通过预测目标元素可能存在的位置来减少查找次数。插值查找利用了数组中元素之间的数值关系来估计目标元素的位置。\n",
    "\n",
    "**插值查找的基本步骤如下：**\n",
    "1. 计算目标元素可能位于的位置 `pos`，公式为 `pos = left + ((target - array[left]) * (right - left) / (array[right] - array[left]))`。\n",
    "2. 如果 `pos` 位置的元素等于目标元素，则查找成功。\n",
    "3. 如果 `pos` 位置的元素大于目标元素，则在左侧子数组中继续查找。\n",
    "4. 如果 `pos` 位置的元素小于目标元素，则在右侧子数组中继续查找。\n",
    "5. 如果 `pos` 超出了数组的范围或 `array[left] == array[right]`，则查找失败。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element 10 found at index 9\n"
     ]
    }
   ],
   "source": [
    "public class InterpolationSearch {\n",
    "\n",
    "    /**\n",
    "     * 插值查找方法\n",
    "     * @param array 有序数组\n",
    "     * @param target 目标元素\n",
    "     * @return 目标元素在数组中的索引，如果没有找到，则返回-1\n",
    "     */\n",
    "    public static int search(int[] array, int target) {\n",
    "        // 使用变量 `left` 和 `right` 来标记当前搜索区间的左右边界\n",
    "        int left = 0;\n",
    "        int right = array.length - 1;\n",
    "        // 检查边界条件，确保 `left` 和 `right` 有效且目标元素在当前范围内\n",
    "        while (left <= right && target >= array[left] && target <= array[right]) {\n",
    "            if (left == right) {\n",
    "                if (array[left] == target) {\n",
    "                    return left;\n",
    "                }\n",
    "                return -1; // 元素不在数组中\n",
    "            }\n",
    "\n",
    "            // 插值查找公式 计算目标元素可能的位置\n",
    "            int pos = left + ((target - array[left]) * (right - left) / (array[right] - array[left]));\n",
    "\n",
    "            // 根据目标元素的位置进行调整\n",
    "            if (array[pos] == target) {\n",
    "                // 如果 array[pos] 等于 target，则找到了目标元素，返回其索引\n",
    "                return pos; // 找到目标元素\n",
    "            } else if (array[pos] < target) {\n",
    "                // 如果 array[pos] 小于 target，则在右半部分继续查找。\n",
    "                left = pos + 1; // 在右侧子数组中查找\n",
    "            } else {\n",
    "                // 如果 array[pos] 大于 target，则在左半部分继续查找\n",
    "                right = pos - 1; // 在左侧子数组中查找\n",
    "            }\n",
    "        }\n",
    "        // 如果 left 和 right 相等且 array[left] 不等于 target，则表示没有找到目标元素，返回 -1\n",
    "        return -1; // 没有找到目标元素\n",
    "    }\n",
    "}\n",
    "\n",
    "// 测试\n",
    "int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};\n",
    "int target = 10;\n",
    "int index = InterpolationSearch.search(data, target);\n",
    "if (index != -1) {\n",
    "    System.out.println(\"Element \" + target + \" found at index \" + index);\n",
    "} else {\n",
    "    System.out.println(\"Element \" + target + \" not found.\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6. 跳跃查找（Jump Search）\n",
    "\n",
    "跳跃查找是一种针对有序数组的查找算法，它结合了线性查找和二分查找的优点。跳跃查找通过“跳跃”方式快速移动到数组中的某个位置，然后再通过线性查找在较小的范围内寻找目标元素。这种方法特别适合于较大的数据集，可以显著减少查找次数。\n",
    "\n",
    "**跳跃查找的基本步骤如下：**\n",
    "1. 确定跳跃步长 `step`，通常为 `sqrt(n)`，其中 `n` 是数组长度。\n",
    "2. 从数组的第一个元素开始，每次向前跳跃 `step` 个元素，直到找到第一个大于或等于目标元素的位置。\n",
    "3. 在该位置之前的一段范围内使用线性查找来精确找到目标元素。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element 10 found at index 9\n"
     ]
    }
   ],
   "source": [
    "public class JumpSearch {\n",
    "\n",
    "    /**\n",
    "     * 跳跃查找方法\n",
    "     * @param array 有序数组\n",
    "     * @param target 目标元素\n",
    "     * @return 目标元素在数组中的索引，如果没有找到，则返回-1\n",
    "     */\n",
    "    public static int search(int[] array, int target) {\n",
    "        int n = array.length;\n",
    "        int step = (int)Math.sqrt(n); // 计算跳跃步长 step，通常是数组长度 n 的平方根\n",
    "        int prev = 0; // 上一次跳跃的位置 （初始化 prev 为0，表示当前跳跃前的位置）\n",
    "\n",
    "        // 每次跳跃 step 个位置 寻找跳跃步长内第一个大于等于目标元素的位置   \n",
    "        while (prev < n && array[Math.min(step, n) - 1] < target) {\n",
    "            prev = step;\n",
    "            // \n",
    "            step += (int)Math.sqrt(n);\n",
    "            if (prev >= n) {\n",
    "                return -1; // 超过数组长度\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // 在找到跳跃步长内第一个大于等于目标元素的位置后，使用线性查找在该位置附近精确查找目标元素\n",
    "        while (array[prev] < target) {\n",
    "            prev++;\n",
    "            // 如果prev超过步长或者数组长度，则目标元素不存在 \n",
    "            if (prev == Math.min(step, n)) {\n",
    "                return -1;\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // 如果找到目标元素，返回其索引 \n",
    "        if (array[prev] == target) {\n",
    "            return prev;\n",
    "        }\n",
    "\n",
    "        return -1; // 没有找到目标元素\n",
    "    }\n",
    "}\n",
    "\n",
    "// 测试\n",
    "int[] data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};\n",
    "int target = 10;\n",
    "int index = JumpSearch.search(data, target);\n",
    "if (index != -1) {\n",
    "    System.out.println(\"Element \" + target + \" found at index \" + index);\n",
    "} else {\n",
    "    System.out.println(\"Element \" + target + \" not found.\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7. 红黑树（Red-Black Tree）\n",
    "\n",
    "红黑树是一种自平衡的二叉查找树，它通过特定的颜色属性来保证树的平衡性。红黑树的每个节点都有一个颜色属性，可以是红色或黑色，这有助于保持树的高度相对较低，从而保证查找、插入和删除操作的时间复杂度为O(log n)。\n",
    "\n",
    "红黑树必须满足以下五个性质：\n",
    "1. **每个节点要么是红色，要么是黑色。**\n",
    "2. **根节点是黑色。**\n",
    "3. **每个叶子节点（NIL节点，空节点）是黑色。**\n",
    "4. **如果一个节点是红色的，则它的两个子节点都是黑色的。（从每个叶子到根的所有路径上不能有两个连续的红色节点）**\n",
    "5. **从任一节点到其每个叶子的所有简单路径都包含相同数量的黑色节点。（所有路径上的黑色节点数量相同，称为黑色高度）**\n",
    "\n",
    "这些性质保证了红黑树的平衡性，即使在频繁的插入和删除操作后也能保持良好的性能。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "After inserting the following keys:\n",
      "10 20 30 40 50 25 \n",
      "In-order traversal of the tree:\n",
      "Key: 10, Color: BLACK\n",
      "Key: 20, Color: BLACK\n",
      "Key: 25, Color: RED\n",
      "Key: 30, Color: BLACK\n",
      "Key: 40, Color: RED\n",
      "Key: 50, Color: BLACK\n",
      "\n",
      "Deleting key 20...\n",
      "In-order traversal after deletion:\n",
      "Key: 10, Color: BLACK\n",
      "Key: 25, Color: BLACK\n",
      "Key: 30, Color: BLACK\n",
      "Key: 40, Color: RED\n",
      "Key: 50, Color: BLACK\n",
      "\n",
      "Deleting key 30...\n",
      "In-order traversal after deletion:\n",
      "Key: 10, Color: BLACK\n",
      "Key: 25, Color: BLACK\n",
      "Key: 40, Color: RED\n",
      "Key: 50, Color: BLACK\n",
      "\n",
      "Deleting key 40...\n",
      "In-order traversal after deletion:\n",
      "Key: 10, Color: BLACK\n",
      "Key: 25, Color: BLACK\n",
      "Key: 50, Color: BLACK\n"
     ]
    }
   ],
   "source": [
    "// 枚举类型表示节点颜色\n",
    "public enum Color { RED, BLACK };\n",
    "\n",
    "// 定义了红黑树的节点，每个节点包含键值 key、颜色 color 以及指向左右子节点和父节点的引用\n",
    "public static class Node {\n",
    "    int key;\n",
    "    Color color;\n",
    "    Node left, right, parent;\n",
    "\n",
    "    public Node(int key, Color color) {\n",
    "        this.key = key;\n",
    "        this.color = color;\n",
    "        left = right = parent = null;\n",
    "    }\n",
    "}\n",
    "\n",
    "public class RedBlackTree {\n",
    "    // 指向树根节点的引用 root\n",
    "    public Node root;\n",
    "    // 初始化根节点为 null\n",
    "    public RedBlackTree() {\n",
    "        root = null;\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 插入新节点 并在插入后调用 fixInsertion 方法来修复可能破坏的红黑树性质\n",
    "     * @param key 要插入的键值\n",
    "     */\n",
    "    public void insert(int key) {\n",
    "        // 创建一个新的红色节点\n",
    "        Node newNode = new Node(key, Color.RED);\n",
    "        Node current = root, parent = null;\n",
    "        // 查找新节点的位置\n",
    "        while (current != null) {\n",
    "            parent = current;\n",
    "            if (newNode.key < current.key) {\n",
    "                current = current.left;\n",
    "            } else {\n",
    "                current = current.right;\n",
    "            }\n",
    "        }\n",
    "        // 设置新节点的父节点\n",
    "        newNode.parent = parent;\n",
    "        if (parent == null) {\n",
    "            root = newNode; // 如果树为空，则新节点成为根节点\n",
    "        } else if (newNode.key < parent.key) {\n",
    "            // 将新节点作为左子节点插入\n",
    "            parent.left = newNode;\n",
    "        } else {\n",
    "            // 将新节点作为右子节点插入\n",
    "            parent.right = newNode;\n",
    "        }\n",
    "\n",
    "        // 修复红黑树性质\n",
    "        fixInsertion(newNode);\n",
    "    }\n",
    "\n",
    "    // 负责在插入节点后重新调整树的结构，以确保红黑树的所有性质得到保持\n",
    "    public void fixInsertion(Node newNode) {\n",
    "        Node parent = null;\n",
    "        while ((parent = newNode.parent) != null && parent.color == Color.RED) {\n",
    "            if (parent == parent.parent.left) {\n",
    "                Node uncle = parent.parent.right;\n",
    "                if (uncle != null && uncle.color == Color.RED) {\n",
    "                    // 情况1: 叔叔节点也是红色，重新着色\n",
    "                    parent.color = Color.BLACK;\n",
    "                    uncle.color = Color.BLACK;\n",
    "                    parent.parent.color = Color.RED;\n",
    "                    newNode = parent.parent;\n",
    "                } else {\n",
    "                    if (newNode == parent.right) {\n",
    "                        // 情况2: 新节点是其父节点的右子节点，进行左旋\n",
    "                        newNode = parent;\n",
    "                        rotateLeft(newNode);\n",
    "                    }\n",
    "                    // 情况3: 新节点是其父节点的左子节点，进行右旋并重新着色\n",
    "                    parent.color = Color.BLACK;\n",
    "                    parent.parent.color = Color.RED;\n",
    "                    rotateRight(parent.parent);\n",
    "                }\n",
    "            } else {\n",
    "                // 对称情况\n",
    "                Node uncle = parent.parent.left;\n",
    "                if (uncle != null && uncle.color == Color.RED) {\n",
    "                    parent.color = Color.BLACK;\n",
    "                    uncle.color = Color.BLACK;\n",
    "                    parent.parent.color = Color.RED;\n",
    "                    newNode = parent.parent;\n",
    "                } else {\n",
    "                    if (newNode == parent.left) {\n",
    "                        newNode = parent;\n",
    "                        rotateRight(newNode);\n",
    "                    }\n",
    "                    parent.color = Color.BLACK;\n",
    "                    parent.parent.color = Color.RED;\n",
    "                    rotateLeft(parent.parent);\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        root.color = Color.BLACK; // 根节点总是黑色\n",
    "    }\n",
    "\n",
    "    // rotateLeft 实现了左旋操作，用于调整树的结构\n",
    "    public void rotateLeft(Node node) {\n",
    "        Node rightChild = node.right;\n",
    "        node.right = rightChild.left;\n",
    "        if (rightChild.left != null) {\n",
    "            rightChild.left.parent = node;\n",
    "        }\n",
    "        rightChild.parent = node.parent;\n",
    "        if (node.parent == null) {\n",
    "            // 如果旋转的是根节点，则更新根节点\n",
    "            root = rightChild;\n",
    "        } else if (node == node.parent.left) {\n",
    "            node.parent.left = rightChild;\n",
    "        } else {\n",
    "            node.parent.right = rightChild;\n",
    "        }\n",
    "        rightChild.left = node;\n",
    "        node.parent = rightChild;\n",
    "    }\n",
    "\n",
    "    // rotateRight 方法实现了右旋操作，用于调整树的结构\n",
    "    public void rotateRight(Node node) {\n",
    "        Node leftChild = node.left;\n",
    "        node.left = leftChild.right;\n",
    "        if (leftChild.right != null) {\n",
    "            leftChild.right.parent = node;\n",
    "        }\n",
    "        leftChild.parent = node.parent;\n",
    "        if (node.parent == null) {\n",
    "            // 如果旋转的是根节点，则更新根节点\n",
    "            root = leftChild;\n",
    "        } else if (node == node.parent.right) {\n",
    "            node.parent.right = leftChild;\n",
    "        } else {\n",
    "            node.parent.left = leftChild;\n",
    "        }\n",
    "        leftChild.right = node;\n",
    "        node.parent = leftChild;\n",
    "    }\n",
    "\n",
    "    // 删除节点\n",
    "    public void delete(int key) {\n",
    "        Node z = findNode(root, key); // 查找要删除的节点\n",
    "        if (z == null) return; // 如果节点不存在则返回\n",
    "\n",
    "        Node y = z;\n",
    "        Color yOriginalColor = z.color; // 初始化 yOriginalColor 为 z 的颜色\n",
    "\n",
    "        Node x = null;\n",
    "\n",
    "        if (z.left == null) {\n",
    "            x = z.right;\n",
    "            transplant(z, z.right);\n",
    "        } else if (z.right == null) {\n",
    "            x = z.left;\n",
    "            transplant(z, z.left);\n",
    "        } else {\n",
    "            y = minimum(z.right); // 找到右子树中的最小节点\n",
    "            yOriginalColor = y.color;\n",
    "            x = y.right;\n",
    "            \n",
    "            if (y.parent == z) {\n",
    "                x.parent = y;\n",
    "            } else {\n",
    "                transplant(y, y.right); // 替换 y 节点\n",
    "                y.right = z.right;\n",
    "                if (y.right != null) {\n",
    "                    y.right.parent = y;\n",
    "                }\n",
    "            }\n",
    "            \n",
    "            transplant(z, y); // 替换 z 节点\n",
    "            y.left = z.left;\n",
    "            if (y.left != null) {\n",
    "                y.left.parent = y;\n",
    "            }\n",
    "            y.color = z.color;\n",
    "        }\n",
    "\n",
    "        if (yOriginalColor == Color.BLACK) {\n",
    "            fixDelete(x); // 修复删除后的红黑树性质\n",
    "        }\n",
    "    }\n",
    "\n",
    "    private void fixDelete(Node x) {\n",
    "        while (x != root && x != null && x.color == Color.BLACK) {\n",
    "            if (x == x.parent.left) {\n",
    "                Node s = x.parent.right;\n",
    "                if (s != null && s.color == Color.RED) {\n",
    "                    s.color = Color.BLACK;\n",
    "                    x.parent.color = Color.RED;\n",
    "                    rotateLeft(x.parent);\n",
    "                    s = x.parent.right;\n",
    "                }\n",
    "                if (s != null && s.left.color == Color.BLACK && s.right.color == Color.BLACK) {\n",
    "                    s.color = Color.RED;\n",
    "                    x = x.parent;\n",
    "                } else {\n",
    "                    if (s != null && s.right.color == Color.BLACK) {\n",
    "                        s.left.color = Color.BLACK;\n",
    "                        s.color = Color.RED;\n",
    "                        rotateRight(s);\n",
    "                        s = x.parent.right;\n",
    "                    }\n",
    "                    if (s != null) {\n",
    "                        s.color = x.parent.color;\n",
    "                        x.parent.color = Color.BLACK;\n",
    "                        s.right.color = Color.BLACK;\n",
    "                        rotateLeft(x.parent);\n",
    "                        x = root;\n",
    "                    }\n",
    "                }\n",
    "            } else {\n",
    "                Node s = x.parent.left;\n",
    "                if (s != null && s.color == Color.RED) {\n",
    "                    s.color = Color.BLACK;\n",
    "                    x.parent.color = Color.RED;\n",
    "                    rotateRight(x.parent);\n",
    "                    s = x.parent.left;\n",
    "                }\n",
    "                if (s != null && s.right.color == Color.BLACK && s.left.color == Color.BLACK) {\n",
    "                    s.color = Color.RED;\n",
    "                    x = x.parent;\n",
    "                } else {\n",
    "                    if (s != null && s.left.color == Color.BLACK) {\n",
    "                        s.right.color = Color.BLACK;\n",
    "                        s.color = Color.RED;\n",
    "                        rotateLeft(s);\n",
    "                        s = x.parent.left;\n",
    "                    }\n",
    "                    if (s != null) {\n",
    "                        s.color = x.parent.color;\n",
    "                        x.parent.color = Color.BLACK;\n",
    "                        s.left.color = Color.BLACK;\n",
    "                        rotateRight(x.parent);\n",
    "                        x = root;\n",
    "                    }\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "        if (x != null) {\n",
    "            x.color = Color.BLACK;\n",
    "        }\n",
    "    }\n",
    "\n",
    "    private void transplant(Node u, Node v) {\n",
    "        if (u.parent == null) {\n",
    "            root = v; // 如果 u 是根节点，则更新根节点\n",
    "        } else if (u == u.parent.left) {\n",
    "            u.parent.left = v;\n",
    "        } else {\n",
    "            u.parent.right = v;\n",
    "        }\n",
    "        if (v != null) {\n",
    "            v.parent = u.parent; // 更新 v 的父节点\n",
    "        }\n",
    "    }\n",
    "\n",
    "    public Node minimum(Node node) { // 返回节点的左子树中的最小节点\n",
    "        while (node.left != null)\n",
    "            node = node.left;\n",
    "        return node;\n",
    "    }\n",
    "\n",
    "    public Node findNode(Node node, int key) { // 查找具有给定键值的节点\n",
    "        if (node == null || node.key == key) {\n",
    "            return node;\n",
    "        }\n",
    "        if (key < node.key) {\n",
    "            return findNode(node.left, key);\n",
    "        } else {\n",
    "            return findNode(node.right, key);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // 遍历打印树中所有元素\n",
    "    public void inOrderTraversal(Node node) {\n",
    "        if (node != null) {\n",
    "            inOrderTraversal(node.left); // 先遍历左子树\n",
    "            System.out.println(\"Key: \" + node.key + \", Color: \" + node.color); // 输出当前节点信息\n",
    "            inOrderTraversal(node.right); // 再遍历右子树\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "//测试\n",
    "public class TestRedBlackTree {\n",
    "\n",
    "    public static void main(String[] args) {\n",
    "        RedBlackTree rbt = new RedBlackTree(); // 创建红黑树实例\n",
    "\n",
    "        // 插入一组键值\n",
    "        int[] keys = {10, 20, 30, 40, 50, 25};\n",
    "        for (int key : keys) {\n",
    "            rbt.insert(key);\n",
    "        }\n",
    "\n",
    "        // 打印插入后的红黑树\n",
    "        System.out.println(\"After inserting the following keys:\");\n",
    "        for (int key : keys) {\n",
    "            System.out.print(key + \" \");\n",
    "        }\n",
    "        System.out.println(\"\\nIn-order traversal of the tree:\");\n",
    "        rbt.inOrderTraversal(rbt.root);\n",
    "\n",
    "        // 删除键值为 20 的节点\n",
    "        System.out.println(\"\\nDeleting key 20...\");\n",
    "        rbt.delete(20);\n",
    "        System.out.println(\"In-order traversal after deletion:\");\n",
    "        rbt.inOrderTraversal(rbt.root);\n",
    "\n",
    "        // 删除键值为 30 的节点\n",
    "        System.out.println(\"\\nDeleting key 30...\");\n",
    "        rbt.delete(30);\n",
    "        System.out.println(\"In-order traversal after deletion:\");\n",
    "        rbt.inOrderTraversal(rbt.root);\n",
    "\n",
    "        // 删除键值为 40 的节点\n",
    "        System.out.println(\"\\nDeleting key 40...\");\n",
    "        rbt.delete(40);\n",
    "        System.out.println(\"In-order traversal after deletion:\");\n",
    "        rbt.inOrderTraversal(rbt.root);\n",
    "    }\n",
    "}\n",
    "\n",
    "TestRedBlackTree.main(new String[] {})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8. B树（B-Tree）\n",
    "\n",
    "B树是一种自平衡的多路搜索树，它设计用于优化磁盘访问。B树的特点是每个节点可以拥有多个子节点，并且每个节点可以存储多个键值。这种结构使得B树非常适合存储大量的数据，并且在磁盘上的读写操作效率较高，因为每次磁盘访问可以获取更多的信息。\n",
    "\n",
    "B树具有以下主要性质：\n",
    "1. **每个节点最多可以有m个子节点。**\n",
    "2. **除了根节点和叶子节点之外，其他每个节点至少有⌈m/2⌉个子节点。**\n",
    "3. **根节点至少有两个子节点（除非它是叶子节点）。**\n",
    "4. **所有叶子节点都在同一层，并且不包含子节点。**\n",
    "5. **每个节点最多可以存储m-1个键值。**\n",
    "6. **每个节点至少存储⌈(m-1)/2⌉个键值（除了根节点外）。**\n",
    "\n",
    "这些性质确保了B树的高度较低，同时保持了良好的平衡性，从而保证了高效的查找、插入和删除操作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[40]\n",
      "   [20]\n",
      "      [10]\n",
      "      [25, 35]\n",
      "   [45]\n",
      "      [30]\n",
      "      [55, 60]\n",
      "Element 35 is found in the tree.\n"
     ]
    }
   ],
   "source": [
    "public class BTree {\n",
    "\n",
    "    private static final int M = 3; // 每个节点的最大子节点数\n",
    "    private static final int MAX_KEYS = M - 1; // 每个节点的最大键值数\n",
    "    private Node root; // 树的根节点\n",
    "\n",
    "    // 定义了B树的节点，每个节点包含一个键值数组 keys、一个子节点数组 children 和一个布尔标志 leaf 来标识是否为叶子节点\n",
    "    private static class Node {\n",
    "        int[] keys; // 存储键值的数组\n",
    "        Node[] children; // 存储子节点的数组\n",
    "        boolean leaf; // 标志是否为叶子节点\n",
    "        int numKeys; // 当前节点实际包含的键值数量\n",
    "\n",
    "        public Node(boolean _leaf) {\n",
    "            leaf = _leaf;\n",
    "            keys = new int[MAX_KEYS]; // 初始化键值数组\n",
    "            children = new Node[M]; // 初始化子节点数组\n",
    "            numKeys = 0; // 初始化键值数量\n",
    "            for (int i = 0; i < M; ++i) {\n",
    "                children[i] = null; // 初始化子节点数组为 null\n",
    "            }\n",
    "        }\n",
    "\n",
    "        public Node() {\n",
    "            this(false); // 默认初始化为非叶子节点\n",
    "        }\n",
    "\n",
    "        // 打印节点的信息\n",
    "        public String toString() {\n",
    "            StringBuilder sb = new StringBuilder(\"[\");\n",
    "            for (int i = 0; i < numKeys; i++) {\n",
    "                if (i > 0) sb.append(\", \");\n",
    "                sb.append(keys[i]);\n",
    "            }\n",
    "            sb.append(\"]\");\n",
    "            return sb.toString();\n",
    "        }\n",
    "    }\n",
    "\n",
    "    public BTree() {\n",
    "        root = new Node(true); // 初始化一个空的B树，根节点为叶子节点\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 插入键值到B树\n",
    "     * 如果根节点已满，则需要分裂根节点\n",
    "     * @param key 要插入的键值\n",
    "     */\n",
    "    public void insert(int key) {\n",
    "        // 如果根节点已满，则需要分裂根节点\n",
    "        if (root.numKeys == root.keys.length) {\n",
    "            Node s = new Node(false); // 创建一个新的非叶子节点\n",
    "            s.children[0] = root; // 设置新节点的第一个子节点为当前根节点\n",
    "            splitChild(s, 0); // 分裂当前根节点\n",
    "            root = s; // 更新根节点为新创建的节点\n",
    "        }\n",
    "        insertNonFull(root, key); // 在根节点上调用插入非满节点的方法\n",
    "    }\n",
    "\n",
    "    // 用于在非满节点中插入键值。如果是叶子节点，直接插入；如果不是叶子节点，则递归插入\n",
    "    private void insertNonFull(Node x, int k) {\n",
    "        int i = x.numKeys - 1; // 初始化索引为最后一个键值的位置\n",
    "        if (x.leaf) {\n",
    "            // 如果是叶子节点，直接插入\n",
    "            while (i >= 0 && k < x.keys[i]) {\n",
    "                x.keys[i + 1] = x.keys[i]; // 向右移动键值\n",
    "                i--;\n",
    "            }\n",
    "            x.keys[i + 1] = k; // 插入新的键值\n",
    "            x.numKeys++; // 增加键值数量\n",
    "        } else {\n",
    "            // 如果不是叶子节点，递归插入\n",
    "            while (i >= 0 && k < x.keys[i]) {\n",
    "                i--; // 找到插入的位置\n",
    "            }\n",
    "            i++; // 调整索引位置\n",
    "            if (x.children[i] == null) {\n",
    "                x.children[i] = new Node(true); // 如果子节点为null，则创建新的叶子节点\n",
    "            }\n",
    "            if (x.children[i].numKeys == x.children[i].keys.length) {\n",
    "                // 如果子节点已满，则需要分裂\n",
    "                splitChild(x, i);\n",
    "                if (k > x.keys[i]) {\n",
    "                    i++; // 如果键值大于分裂后的新键值，则调整插入位置\n",
    "                }\n",
    "            }\n",
    "            insertNonFull(x.children[i], k); // 在子节点中递归插入\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // 用于分裂一个已满的子节点，并将分裂后的子节点添加到父节点中\n",
    "    private void splitChild(Node x, int i) {\n",
    "        Node y = x.children[i]; // 获取需要分裂的子节点\n",
    "        Node z = new Node(y.leaf); // 创建一个新的子节点\n",
    "        x.children[i + 1] = z; // 将新节点添加到父节点的子节点数组中\n",
    "        x.keys[i] = y.keys[y.numKeys / 2]; // 把子节点中间的键值提升到父节点\n",
    "        x.numKeys++; // 增加键值数量\n",
    "\n",
    "        // 移动子节点的下半部分到新的节点z\n",
    "        int numKeys = y.numKeys;\n",
    "        for (int j = 0; j < numKeys / 2; j++) {\n",
    "            z.keys[j] = y.keys[j + numKeys / 2]; // 复制下半部分的键值\n",
    "            y.keys[j + numKeys / 2] = 0; // 清除原位置的键值\n",
    "            y.numKeys--; // 减少键值数量\n",
    "        }\n",
    "\n",
    "        // 如果不是叶子节点，还要复制子节点\n",
    "        if (!y.leaf) {\n",
    "            for (int j = 0; j <= numKeys / 2; j++) {\n",
    "                z.children[j] = y.children[j + numKeys / 2]; // 复制下半部分的子节点\n",
    "                y.children[j + numKeys / 2] = null; // 清除原位置的子节点\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // 调整原节点的键值数组\n",
    "        y.keys = Arrays.copyOf(y.keys, y.keys.length);\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 查找特定的键值\n",
    "     * @param key 要查找的键值\n",
    "     * @return 如果找到该键值，返回 true；否则返回 false\n",
    "     */\n",
    "    public boolean search(int key) {\n",
    "        return searchRecursive(root, key);\n",
    "    }\n",
    "\n",
    "    private boolean searchRecursive(Node x, int key) {\n",
    "        int i = 0;\n",
    "        while (i < x.numKeys && key > x.keys[i]) {\n",
    "            i++;\n",
    "        }\n",
    "        if (i < x.numKeys && key == x.keys[i]) {\n",
    "            return true; // 找到了键值\n",
    "        } else if (x.leaf) {\n",
    "            return false; // 到达叶子节点但未找到键值\n",
    "        } else {\n",
    "            return searchRecursive(x.children[i], key); // 递归查找\n",
    "        }\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 打印B树的结构\n",
    "     */\n",
    "    public void printStructure() {\n",
    "        printStructureRecursive(root, 0);\n",
    "    }\n",
    "\n",
    "    private void printStructureRecursive(Node x, int level) {\n",
    "        if (x == null) return;\n",
    "        for (int i = 0; i < level; i++) {\n",
    "            System.out.print(\"   \"); // 缩进\n",
    "        }\n",
    "        System.out.println(x); // 打印当前节点\n",
    "        for (int i = 0; i < x.children.length; i++) {\n",
    "            if (x.children[i] != null) {\n",
    "                printStructureRecursive(x.children[i], level + 1);\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "\n",
    "// 测试\n",
    "BTree bTree = new BTree();\n",
    "int[] keys = {10, 20, 30, 40, 50, 25, 35, 45, 55, 60};\n",
    "for (int key : keys) {\n",
    "    bTree.insert(key);\n",
    "}\n",
    "// 打印树的结构\n",
    "bTree.printStructure();\n",
    "// 查找特定的键值\n",
    "int searchKey = 35;\n",
    "if (bTree.search(searchKey)) {\n",
    "    System.out.println(\"Element \" + searchKey + \" is found in the tree.\");\n",
    "} else {\n",
    "    System.out.println(\"Element \" + searchKey + \" is not found in the tree.\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9. B+树（B+-Tree）\n",
    "\n",
    "B+树是B树的一种变体，它主要用于数据库索引和其他需要高效磁盘访问的应用中。与B树相比，B+树有一些重要的不同之处：\n",
    "- 所有数据项都存储在叶子节点中。\n",
    "- 叶子节点之间通过指针相连，形成一个链表。\n",
    "- 内部节点仅用于指导搜索，不存储数据。\n",
    "\n",
    "这些特性使得B+树在进行范围查询时更加高效，因为可以通过遍历叶子节点之间的链接来快速找到所需的数据。\n",
    "\n",
    "B+树具有以下主要性质：\n",
    "1. **每个节点最多可以有m个子节点。**\n",
    "2. **除了根节点和叶子节点之外，其他每个节点至少有⌈m/2⌉个子节点。**\n",
    "3. **根节点至少有两个子节点（除非它是叶子节点）。**\n",
    "4. **所有叶子节点都在同一层，并且通过双向指针相连。**\n",
    "5. **每个节点最多可以存储m-1个键值。**\n",
    "6. **每个节点至少存储⌈(m-1)/2⌉个键值（除了根节点外）。**\n",
    "7. **数据项只存储在叶子节点中。**\n",
    "\n",
    "这些性质确保了B+树的高度较低，同时保持了良好的平衡性，从而保证了高效的查找、插入和删除操作。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Key 20 found: true\n",
      "Key 10 found: true\n",
      "Key 5 found: true\n",
      "Key 30 found: true\n",
      "Key 25 found: true\n",
      "Key 15 found: true\n",
      "Key 35 found: true\n",
      "Key 40 found: true\n",
      "Key 45 found: true\n",
      "Key 50 found: true\n",
      "Key 100 found: false\n",
      "Key 200 found: false\n",
      "Key 300 found: false\n"
     ]
    }
   ],
   "source": [
    "import java.util.ArrayList;\n",
    "import java.util.Collections;\n",
    "import java.util.List;\n",
    "\n",
    "// BPlusNode 表示 B+ 树中的节点\n",
    "class BPlusNode  {\n",
    "    boolean isLeaf; // 判断是否为叶子节点\n",
    "    List<Integer> keys; // 节点中的键\n",
    "    List<BPlusNode> children; // 子节点\n",
    "    BPlusNode next; // 指向下一个叶子节点的指针\n",
    "\n",
    "    // 构造函数，初始化节点\n",
    "    BPlusNode(boolean isLeaf) {\n",
    "        this.isLeaf = isLeaf;\n",
    "        this.keys = new ArrayList<>();\n",
    "        this.children = new ArrayList<>();\n",
    "        this.next = null;\n",
    "    }\n",
    "}\n",
    "\n",
    "// BPlusTree 表示 B+ 树\n",
    "public class BPlusTree {\n",
    "    private final int ORDER; // 树的阶，即每个节点最多的孩子数\n",
    "    private BPlusNode root; // 树的根节点\n",
    "\n",
    "    // 构造函数，初始化 B+ 树\n",
    "    public BPlusTree(int order) {\n",
    "        this.ORDER = order;\n",
    "        this.root = new BPlusNode(true); // 初始时根节点为叶子节点\n",
    "    }\n",
    "\n",
    "    // 插入一个键到 B+ 树中\n",
    "    public void insert(int key) {\n",
    "        BPlusNode root = this.root;\n",
    "        // 如果根节点已满，则需要分裂根节点\n",
    "        if (root.keys.size() == ORDER - 1) {\n",
    "            BPlusNode newRoot = new BPlusNode(false); // 创建新的根节点\n",
    "            newRoot.children.add(root); // 将旧根节点作为新根节点的子节点\n",
    "            splitChild(newRoot, 0); // 分裂旧根节点\n",
    "            this.root = newRoot; // 更新树的根节点\n",
    "        }\n",
    "        insertNonFull(this.root, key); // 在新的或未满的根节点中插入键\n",
    "    }\n",
    "\n",
    "    // 在非满节点中插入键\n",
    "    private void insertNonFull(BPlusNode node, int key) {\n",
    "        if (node.isLeaf) { // 如果当前节点是叶子节点\n",
    "            int i = 0;\n",
    "            // 查找插入位置\n",
    "            while (i < node.keys.size() && key > node.keys.get(i)) {\n",
    "                i++;\n",
    "            }\n",
    "            node.keys.add(i, key); // 插入键\n",
    "            // 如果叶子节点满了，需要分裂\n",
    "            if (node.keys.size() > ORDER - 1) {\n",
    "                splitLeaf(node);\n",
    "            }\n",
    "        } else { // 如果当前节点不是叶子节点\n",
    "            int i = 0;\n",
    "            // 查找子节点\n",
    "            while (i < node.keys.size() && key > node.keys.get(i)) {\n",
    "                i++;\n",
    "            }\n",
    "            BPlusNode child = node.children.get(i); // 找到要插入的子节点\n",
    "            // 如果子节点满了，需要分裂\n",
    "            if (child.keys.size() == ORDER - 1) {\n",
    "                splitChild(node, i);\n",
    "                // 分裂后，可能需要更新子节点\n",
    "                if (key > node.keys.get(i)) {\n",
    "                    child = node.children.get(i + 1);\n",
    "                }\n",
    "            }\n",
    "            insertNonFull(child, key); // 在子节点中递归插入\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // 分裂指定的子节点\n",
    "    private void splitChild(BPlusNode parent, int index) {\n",
    "        BPlusNode fullChild = parent.children.get(index); // 要分裂的子节点\n",
    "        BPlusNode newChild = new BPlusNode(fullChild.isLeaf); // 创建新的子节点\n",
    "        int mid = ORDER / 2; // 计算中间位置\n",
    "\n",
    "        // 将键和子节点分配到新子节点\n",
    "        parent.keys.add(index, fullChild.keys.get(mid));\n",
    "        parent.children.add(index + 1, newChild);\n",
    "\n",
    "        for (int i = mid + 1; i < fullChild.keys.size(); i++) {\n",
    "            newChild.keys.add(fullChild.keys.get(i));\n",
    "        }\n",
    "        fullChild.keys.subList(mid, fullChild.keys.size()).clear(); // 清除旧子节点的键\n",
    "\n",
    "        // 如果不是叶子节点，也需要分裂子节点\n",
    "        if (!fullChild.isLeaf) {\n",
    "            for (int i = mid + 1; i < fullChild.children.size(); i++) {\n",
    "                newChild.children.add(fullChild.children.get(i));\n",
    "            }\n",
    "            fullChild.children.subList(mid + 1, fullChild.children.size()).clear(); // 清除旧子节点的子节点\n",
    "        }\n",
    "    }\n",
    "\n",
    "    // 分裂叶子节点\n",
    "    private void splitLeaf(BPlusNode leaf) {\n",
    "        BPlusNode newLeaf = new BPlusNode(true); // 创建新的叶子节点\n",
    "        int mid = ORDER / 2; // 计算中间位置\n",
    "\n",
    "        // 将键移到新叶子节点\n",
    "        for (int i = mid; i < leaf.keys.size(); i++) {\n",
    "            newLeaf.keys.add(leaf.keys.get(i));\n",
    "        }\n",
    "        leaf.keys.subList(mid, leaf.keys.size()).clear(); // 清除旧叶子节点的键\n",
    "\n",
    "        // 更新叶子节点链表\n",
    "        newLeaf.next = leaf.next;\n",
    "        leaf.next = newLeaf;\n",
    "    }\n",
    "\n",
    "    // 查找键是否存在\n",
    "    public boolean search(int key) {\n",
    "        return search(root, key);\n",
    "    }\n",
    "\n",
    "    // 在指定节点中查找键\n",
    "    private boolean search(BPlusNode node, int key) {\n",
    "        int i = 0;\n",
    "        // 查找键的位置\n",
    "        while (i < node.keys.size() && key > node.keys.get(i)) {\n",
    "            i++;\n",
    "        }\n",
    "        // 如果找到键，则返回 true\n",
    "        if (i < node.keys.size() && node.keys.get(i) == key) {\n",
    "            return true;\n",
    "        } else if (node.isLeaf) { // 如果到达叶子节点仍未找到，则返回 false\n",
    "            return false;\n",
    "        } else {\n",
    "            return search(node.children.get(i), key); // 递归查找子节点\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "\n",
    "// 测试 B+ 树的功能\n",
    "BPlusTree bpt = new BPlusTree(4); // 创建阶为 4 的 B+ 树\n",
    "// 插入测试数据\n",
    "int[] keys = {20, 10, 5, 30, 25, 15, 35, 40, 45, 50};\n",
    "for (int key : keys) {\n",
    "    bpt.insert(key);\n",
    "}\n",
    "// 查找测试数据\n",
    "for (int key : keys) {\n",
    "    System.out.println(\"Key \" + key + \" found: \" + bpt.search(key));\n",
    "}\n",
    "// 查找不存在的键\n",
    "int[] searchKeys = {100, 200, 300};\n",
    "for (int key : searchKeys) {\n",
    "    System.out.println(\"Key \" + key + \" found: \" + bpt.search(key));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10. B-树（B-Tree）\n",
    "\n",
    "实际上，B-树和B+树的概念有些混淆，通常所说的B-树指的是标准的B树，而B+树是B树的一种变体。B-树（B-Tree）在概念和性质上与标准B树一致，只是名称上有所不同。在实际应用中，通常提到的B树是指标准B树，而B+树是指上述实现的B+树。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "java",
   "pygments_lexer": "java",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
